/*
 * unionfind.h
 *
 *  Created on: Jun 7, 2011
 *      Author: timothy
 */

#ifndef UNION_H
#define UNION_H

#include <omp.h>
#include <vector>

#include "init.h"

class Shingle;

// Comment/Uncomment this line to determine if singletons should be merged into an adjacent group.
#define MERGE_ON_SINGLETONS

class UnionFindEntry
{
	private:
		omp_lock_t lock;

	public:
		// FIELDS //
		unsigned long ID;
		UnionFindEntry *Group;
		long GroupID;
		int Size;
		int NumberOfEdges;

		// Return values:
		//   1 - Success
		//   0 - Failure, we are already locked for the target we were about to wait on.
		//   WAITS - Already locked for another target.
		void Lock();
		void Unlock();
		void ForceJoin(UnionFindEntry *target);
		UnionFindEntry *PathCompress();
		// CONSTRUCTORS //
		UnionFindEntry(unsigned long ID);
		~UnionFindEntry();

		// METHODS //
		void Join(UnionFindEntry *target);
};

class UnionFindTree
{
	private:
		UnionFindEntry** array;
		int Size;
		int nextGroupID;
		int groups;
		int singletons;
		std::vector<int*> GroupSizes;
	public:
	// FIELDS //
		int TotalEdges;
		int ExternalEdges;
		int SingletonEdges;
		long numCulledInserts[MAX_THREADS_DEBUG];
		long numUnculledInserts[MAX_THREADS_DEBUG];

	// CONSTRUCTORS //
		UnionFindTree(int size);
		~UnionFindTree();

	// METHODS //
		void Insert(Shingle *insert, int nthShingle);
		void Join(unsigned long a, unsigned long b);

		int GetGroupID(unsigned long index);
		int GetNumberOfGroups();
		int GetNumberOfSingletons();
		void AddVertexToAudit(unsigned long vertex);
		void AddEdgeToAudit(unsigned long from, unsigned long to);
		void AuditGroupSizes();
		void AuditEdges();
};

#endif
